package seqlist.双向链表;
/**
 * 基于int的双向链表 - 火车
 * 真正被用户使用的是火车类-双向链表对象
 */
public class Double_Linked_list {

    // 有效节点的个数
    private int size;
    // 当前头节点
    private DoubleNode head;
    // 当前尾节点
    private DoubleNode tail;

    // 在双向链表的头部插入新节点
    public void addFirst(int val){
        //直接用构造方法快速赋值
        DoubleNode node = new DoubleNode(null,val,head);

//        if(head == null || tail == null){
//            //链表中没有节点时
//            head = tail = node;
//        }else{
//            //以前的头节点的前驱地址连接新的节点位置
//            head.prve = node;
//            head = node;//新节点成为新的头节点
//        }

        //精简写法
        if(tail == null){
           // 链表中没有节点时
            tail = node;
        }else{
            head.prve = node;//以前的头节点的前驱地址连接新的节点位置
        }
        head = node; // 对于头插来说，最终无论链表是否为空。head = node
        size++;
    }

    // 在双向链表的尾部插入新节点
    public void addLast(int val){
        DoubleNode node = new DoubleNode(tail, val, null);//直接用构造方法快速赋值
        if(head == null){
            head = node;
        }else{
            tail.next = node;
        }
        tail = node;
        size ++;
    }

    /**
     * 在 index 索引处插入一个节点
     */
    public void add(int index, int val){
        //判断索引的合法性
        if(index < 0 || index > size){
            System.out.println("插入的索引值错误");
            return;
        }
        if(index == 0){
            addFirst(val);
        }else if(index == size){
            addLast(val);
        }else{
            //到这里说明此时至少有三个节点
            DoubleNode node = node(index);//索引位置处的节点。
            DoubleNode cur = new DoubleNode(node.prve, val, node);//新节点
            //在new这个对象的时候就已经用构造方法连接好两条线了。
            node.prve.next = cur;//前驱连接新节点
            node.prve = cur;//待插入位置的节点连接新节点
            size ++;
        }
    }

    //根据索引值返回对于节点的地址,不存在则返回 null
    private DoubleNode node(int index){
        DoubleNode x = null;
        if(index < size / 2){
          //从前往后走找需要 index 步
          x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
        }else{
            //从后往前走找需要 size - 1 - index 步
            x = tail;
            for (int i = size - 1; i > index ; i--) {
                //注意：这里不再是用next了而且前地址prve
                 x = x.prve;
            }
        }
        return x;
    }

    /**
     * 查询第一个值为 val的索引为多少
     * 不存在则返回 -1
     */
    public int getByValue(int val){
        DoubleNode rep = head;
        for (int i = 0; i < size; i++) {
                if(rep.val == val){
                    return i;
                }
             rep = rep.next;
        }

        return -1;  //循环里面没找到就代表不存在
    }

    /**
     * 查询索引为index处的节点值为多少
     */
    public int get(int index){
        if(rangeCheck(index)){
         return node(index).val;
        }
        return -1;
    }

    /**
     * 查询是否包含指定值的节点
     */
    public boolean contains(int val){
        return getByValue(val) != -1;
    }

    /**
     * 判断给的index索引是否合理
     */
    private boolean rangeCheck(int index){
        if(index < 0 || index >= size){
            return false;
        }
        return true;
    }

    /**
     * 修改索引为index位置的结点值为 newVal，返回修改前的节点值
     */
    public int set(int index, int newVal){
        DoubleNode cur = node(index);
        int rep = cur.val;
        cur.val = newVal;
        return rep;
    }

    //删除当前双向链表中的node节点
    private void unlink(DoubleNode node){
        // 1.前空后空
        // 2.前不空后空
        // 3.前不空后不空
        // 4.前空后不空
        DoubleNode prve = node.prve;//前驱
        DoubleNode next = node.next;//后继
        //现在删除就有三种情况，头节点，尾节点.注释：这里的前部分和后部分都是以node为中心的
        //先处理前半部分
        if(prve == null){
            //删除的是头节点,那就更新头节点位置
            head = next;//头节点变为后继节点
            //注释：这里不要着急断开原来头节点的next连接，那算后半部分
            //现在这里只处理前半部分
        }else{
            // 前驱不为空的情况
            prve.next = next;
            node.prve = null;//断开连接
        }

        //现在处理后半部分
        if(next == null){
            //删除的是尾节点,那就更新尾节点位置
            tail = prve;
        }else{
            // 后继不为空的情况
            next.prve = prve;
            node.next = null;//断开连接
        }
        size --;
    }

    //删除 index 处的节点,并返回删除的节点值
    public int remove(int index){
        if(rangeCheck(index)){
            DoubleNode node = node(index);//返回索引处的节点地址
            int rep = node.val;
            unlink(node);
            return rep;
        }
        System.out.println("输入删除的索引错误");
        return -1;
    }

    //头删
    public int removeFrist(){
        return remove(0);
    }

    //尾删
    public int removeLast(){ return remove(size - 1); }

    //删除出现第一个值为val的结点
    public void removeValueOnce(int val){
        for (DoubleNode x = head; x != null ; x = x.next) {
            if(x.val == val){
                unlink(x);
                break;
            }
        }
    }

    //删除全部值为 val 的节点
    public void removeAllValue(int val) {
        for (DoubleNode x = head; x != null; ) {
            if (x.val == val) {
                // x就是待删除的结点
                //当前的节点要被删除，保存它下一个节点地址
                DoubleNode successor = x.next;
                unlink(x);
                x = successor;//让循环的x连接上后面的链表
            } else {
                x = x.next;
            }

        }
    }
    //注释：我们unlink删除节点时吧它连接的全断开了
    //要删除全部的val时会发生什么？ 当时的在循环中的链表
    //直接失去的后继节点的地址，所以我们要在unlink的时候保存下一个节点地址

    //补充toString方法打印链表
    public String toString(){
        String rep = "";
        for (DoubleNode x = head; x != null ; x = x.next) {
            rep += x.val;
            rep += " -> ";
        }
        rep += "NULL";
        return rep;
    }

}




/**
 * 单链表的具体的每个节点 - 车厢类
 */
class DoubleNode {

    // 前驱节点
    DoubleNode prve;
    // 当前节点值
    int val;
    // 后继节点
    DoubleNode next;

    // alt + insert 快捷键

    //无参构造
    public DoubleNode() {
    }

    //有参构造
    public DoubleNode(int val) {
        this.val = val;
    }

    //有参构造
    public DoubleNode(DoubleNode prve, int val, DoubleNode next) {
        this.prve = prve;
        this.val = val;
        this.next = next;
    }
}